#include<string>
#include<iostream>
using namespace std;

class Trie
{
public:
    Trie* next[26] = {};
    bool v;
    Trie()
    {
        for(int i=0;i<26;i++)
        {
            next[i] = NULL;
        }
        v = false;
    }
    void add(char c)
    {
        next[c-'a'] = new Trie;
    }
    Trie* get(char c)
    {
        return next[c-'a'];
    }
} ;

class WordDictionary {
private:
    Trie* root = new Trie;
public:
    // Adds a word into the data structure.
    void addWord(string word) {
        Trie* before = root;
        int i;
        for(char ch:word)
        {
            i = ch-'a';
            if(!before->next[i])
                before->next[i] = new Trie;
            before = before->next[i];                
        }
         before->v = true;
    }

    bool search(Trie* _root,string& word,int pos)
    {
        if(!_root)    return false;
        if(pos==word.length())    return _root->v;
        if(word[pos]=='.')
        {         
            for(Trie* tmp:_root->next)
            {               
                if(tmp)
                {
                    if(search(tmp,word,pos+1)) return true;
                }
            }
            return false;
        }           
        return _root->get(word[pos]) ? search(_root->get(word[pos]),word,pos+1):false;
    }

    bool search(string word) {
        return search(root,word,0);
    }
};

int main()
{
    cout<<"boy"<<endl;
    WordDictionary wd;
    cout<<"hey"<<endl;
    wd.addWord("sb");
    cout<<"sb"<<endl;
    cout << wd.search("sb") << endl;
}